//
//  Problem15.swift
//  LeetCode 15. 三数之和
//
//  Created by 武侠 on 2020/8/19.
//  Copyright © 2020 zhulongiMac02. All rights reserved.
//

import UIKit

/*
 15. 三数之和
 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
 注意：答案中不可以包含重复的三元组。

 示例：
 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
 满足要求的三元组集合为：
 [
   [-1, 0, 1],
   [-1, -1, 2]
 ]
 */
class Problem15: NSObject {
    func solution() {
//        print(threeSum([-1, 0, 1, 2, -1, -4]))
//        print(threeSum([1,-1,-1,0]))
        print(threeSum([0,0,0]))
    }
    
    // 暴力接发，3层循环♻️
    func threeSum(_ nums: [Int]) -> [[Int]] {
        var reList:[[Int]] = []
        if nums.count < 3 {
            return reList
        }
        
        // 1: 现将数组排序
        let sNums = nums.sorted()
        print(sNums)
        
        // 2: 3层循环
        for var i in 0..<sNums.count-2 {
            // 过滤 相等的，节约判断
            if i != 0 && sNums[i] == sNums[i-1] {
                continue
            }
            for var j in i+1..<sNums.count-1 {
                if j != i+1 && sNums[j] == sNums[j-1] {
                    continue
                }
                for var l in j+1..<sNums.count {
                    if l != j+1 && sNums[l] == sNums[l-1] {
                        continue
                    }
                    print("i = \(i), nums[i] = \(sNums[i])")
                    print("j = \(j), nums[j] = \(sNums[j])")
                    print("l = \(l), nums[l] = \(sNums[l])")
                    print("")
                    if sNums[i] + sNums[j] + sNums[l] == 0 {
                        let list = [sNums[i], sNums[j], sNums[l]]
//                        if self.contaisList(reList, list: list) == false {
                            reList.append(list)
//                        }
                    }
                }
            }
        }
        return reList
    }
    
    // 暴力改进，2层循环♻️：
    // 第二层变成 left指针 和right指针
    // 原理：如果 a + b + c = 0, 继续b1 > b, 那么c1肯定小于c
    func threeSum2(_ nums:[Int]) -> [[Int]] {
        var reList:[[Int]] = []
        if nums.count < 3 {
            return reList
        }
        
        let sNums = nums.sorted()
        for i in 0..<sNums.count {
            if i != 0 && sNums[i] == sNums[i-1] {
                continue
            }
            var j = i+1
            var l = sNums.count - 1
            let target = -sNums[i]
            
            while j < l {
                if j != i+1 && sNums[j] == sNums[j-1] {
                    j += 1
                    continue
                }
                
                if sNums[j] + sNums[l] == target {
                    reList.append([sNums[i], sNums[j], sNums[l]])
                    j += 1
                    l -= 1
                } else if sNums[j] + sNums[l] < target {
                    j += 1
                } else  {
                    l -= 1
                }
            }
            
        }
        
        return reList
    }
    
    
    // 判断是否重复
    func contaisList(_ reList:[[Int]], list:[Int]) -> Bool {
        for subList in reList {
            if subList[0] == list[0] && subList[1] == list[1] && subList[2] == list[2]{
                return true
            }
        }
        return false
    }
}
